home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / C / ESPRESSO.ZIP / GASP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-03-14  |  1.6 KB  |  54 lines
  1. /*
  2.     module: gasp.c
  3.  
  4.     The "last_gasp" heuristic computes the reduction of each cube in
  5.     the cover (without replacement) and then performs an expansion of
  6.     these cubes.  The cubes which expand to cover some other cube are
  7.     added to the original cover and irredundant finds a minimal subset.
  8.  
  9.     If one of the reduced cubes expands to cover some other reduced
  10.     cube, then the new prime thus generated is a candidate for reducing
  11.     the size of the cover.
  12.  
  13.     The expansion expands all cubes (even those that get covered), and
  14.     returns only those cubes which succeed in covering some other cube.
  15. */
  16. #include "espresso.h"
  17.  
  18. /* reduce_gasp -- return a cover of the reduction of each cube of F */
  19. pcover reduce_gasp(F, D)
  20. pcover F, D;
  21. {
  22.     pcube p, last, cunder, *FD;
  23.     pcover G = new_cover(F->count);
  24.  
  25.     /* Reduce cubes of F without replacement -- save those that reduce */
  26.     FD = cube2list(F, D);
  27.     foreach_set(F, last, p) {
  28.         cunder = reduce_cube(FD, p);
  29.         if (! setp_equal(cunder, p))
  30.             G = sf_addset(G, cunder);
  31.         free_cube(cunder);
  32.     }
  33.     free_cubelist(FD);
  34.     return G;
  35. }
  36.  
  37.  
  38. /* expand_gasp -- re-expand the set of cubes which was reduceable */
  39. pcover expand_gasp(G, R)
  40. pcover G, R;
  41. {    return sf_dupl(expand(G, R, TRUE, FALSE));}
  42.  
  43.  
  44. /* irred_gasp -- Add new primes to F and find an irredundant subset */
  45. pcover irred_gasp(F, D, G)
  46. pcover F, D, G;                 /* G is disposed of */
  47. {
  48.     if (G->count != 0)
  49.         F = irredundant(sf_append(F, G), D);
  50.     else
  51.         free_cover(G);
  52.     return F;
  53. }
  54.